//
// Created by liushuai on 2021/1/27.
//

#include "longestSubstring.h"

int longestSubstring(string x, string y) {
    if(x.empty()||y.empty())
        return 0;
    int x_size = x.size();
    int y_size = y.size();

    vector<int> rows(y_size + 1, 0);
    vector<vector<int>> DP(x_size + 1, rows);

    for (int i = 0; i < x.size(); i++) {
        for (int j = 0; j < y.size(); j++) {
            if(!i||!j)
                DP[i][j] = 0;
            else{
                if(x[i]==y[j])
                    DP[i][j] = DP[i-1][j-1]+1;
                else
                    DP[i][j] = DP[i-1][j]>DP[i][j-1]?DP[i-1][j]:DP[i][j-1];
            }
        }
    }
    return DP[x_size-1][y_size-1];

}